#include "../tools.h"
using std::max;

class Solution {
public:


    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text2.size() + 1, vector<int>(text1.size() + 1, -1));
        // base
        dp[text2.size()] = vector<int>(text1.size() + 1, 0);
        for(int i = 0; i < text2.size() + 1; ++i)
            dp[i][text1.size()] = 0;
        // show(dp);

        for(int i = text1.size() - 1; i > -1; --i){
            for(int j = text2.size() - 1; j > -1; --j){
                if(text1[i] == text2[j]){
                    dp[j][i] = dp[j + 1][i + 1] + 1;
                }else{
                    dp[j][i] = max(dp[j+1][i], dp[j][i+1]);
                }
            }
        }

        // show(dp);

        return 0;
    }
};


int main(int argc, char const *argv[])
{
    string text1 = "zabcde", text2 = "acez";

    Solution s;
    s.longestCommonSubsequence(text1, text2);

    return 0;
}
